package primary.code08;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 问题：
 * <p>
 * 获取某个元素左右两侧最近较大值
 * <p>
 * 数据结构：单调栈
 * <p>
 * 栈中保存数组的下标链表/下标（无重复时）；
 * 保持栈中的数据从底向顶递减；
 * 弹出栈元素下标时，即可求的该元素左右侧最近较大值；
 */
@Slf4j
public class Code07_greaterNearest {

    public static void greaterNearest(int[] arr) {
        //省略参数合法性验证...

        Stack<LinkedList<Integer>> decreaseStack = new Stack<>(); // 单调递减栈
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            while (!decreaseStack.isEmpty() && num > arr[decreaseStack.peek().getLast()]) {
                LinkedList<Integer> pop = decreaseStack.pop();
                for (int j = pop.size() - 1; j >= 0; j--) {
                    log.info("index: {}, value:{} 右侧最近大于自身的值是 index: {}, value:{}",
                            pop.get(j), arr[pop.get(j)], i, arr[i]);
                    log.info("index: {}, value:{} 左侧最近大于自身的值是 index: {}, value:{}",
                            pop.get(j), arr[pop.get(j)], decreaseStack.isEmpty() ? null : decreaseStack.peek().getLast(), decreaseStack.isEmpty() ? null : arr[decreaseStack.peek().getLast()]);
                }
            }
            if (!decreaseStack.isEmpty() && num == arr[decreaseStack.peek().getLast()]) {
                decreaseStack.peek().addLast(i);
            } else {
                decreaseStack.push(new LinkedList<>(Arrays.asList(i)));
            }
        }
        while (!decreaseStack.isEmpty()) {
            LinkedList<Integer> pop = decreaseStack.pop();
            for (int j = pop.size() - 1; j >= 0; j--) {
                log.info("index: {}, value:{} 右侧最近大于自身的值是 index: {}, value:{}",
                        pop.get(j), arr[pop.get(j)], null, null);
                log.info("index: {}, value:{} 左侧最近大于自身的值是 index: {}, value:{}",
                        pop.get(j), arr[pop.get(j)], decreaseStack.isEmpty() ? null : decreaseStack.peek().getLast(), decreaseStack.isEmpty() ? null : arr[decreaseStack.peek().getLast()]);
            }
        }

    }

    public static void main(String[] args) {
        /*
            index: 1, value:3 右侧最近大于自身的值是 index: 2, value:6
            index: 1, value:3 左侧最近大于自身的值是 index: 0, value:5
            index: 0, value:5 右侧最近大于自身的值是 index: 2, value:6
            index: 0, value:5 左侧最近大于自身的值是 index: null, value:null
            index: 3, value:1 右侧最近大于自身的值是 index: 4, value:5
            index: 3, value:1 左侧最近大于自身的值是 index: 2, value:6
            index: 4, value:5 右侧最近大于自身的值是 index: 5, value:7
            index: 4, value:5 左侧最近大于自身的值是 index: 2, value:6
            index: 2, value:6 右侧最近大于自身的值是 index: 5, value:7
            index: 2, value:6 左侧最近大于自身的值是 index: null, value:null
            index: 5, value:7 右侧最近大于自身的值是 index: 6, value:8
            index: 5, value:7 左侧最近大于自身的值是 index: null, value:null
            index: 7, value:3 右侧最近大于自身的值是 index: null, value:null
            index: 7, value:3 左侧最近大于自身的值是 index: 6, value:8
            index: 6, value:8 右侧最近大于自身的值是 index: null, value:null
            index: 6, value:8 左侧最近大于自身的值是 index: null, value:null
            */
        greaterNearest(new int[]{5, 3, 6, 1, 5, 7, 8, 3});
    }
}
